import numpy as np
from numpy.linalg import norm

def correlate(array1, array2):
    '''Moves the array2 (template) over the array1 (search image) and computes
    normalized cross correlation between the template and an underlying window
    from the search image at each pixel.
    '''
    SH = array1.shape[0] # search image height
    SW = array1.shape[1] # search image width
    
    TH = array2.shape[0] # template height
    TW = array2.shape[1] # template width
    HALF_TH = TH / 2
    HALF_TW = TW / 2
    
    ZS = np.zeros((SH + TH - 1, SW + TW - 1)) # zero padded search image
    ZS[HALF_TH:HALF_TH + SH,HALF_TW:HALF_TW + SW] = array1
    
    # correlation, the output - same size as the search image
    C = np.zeros(array1.shape)
    
    # function for cutting a window from ZS
    def get_window(x, y):
        return ZS[y:y + TH, x:x + TW]
    
    # compute the normalized cross correlation at each pixel
    for y in range(SH):
        for x in range(SW):
            C[y, x] = _normxcorr(get_window(x, y).flatten(), array2.flatten())
    
    return C

def _normxcorr(u, v):
    '''Returns a normalized cross correlation coefficient of two vectors of the same size.'''
    return np.inner(u / norm(u), v / norm(v))